package DynamicProgramming;//给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
//
// 说明： 
//
// 
// 拆分时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 
//
// 示例 2： 
//
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//     注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 👍 1200 👎 0

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

//leetcode submit region begin(Prohibit modification and deletion)
class wordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        /**
         * 动态规划
         * dp[j]=true 表示[0,j]可以被空格拆分为集合的字符串，否则为false
         * 可知当i>j时，dp[i]的值取决于dp[j]&&isWord(j,i);
         * isWord(j,i)为wordDict.contains(s.substring(j, i))，看这个之间的字符串是否在集合中 
         * */
        int len = s.length();
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        //j表示切分起点，i表示被切分的终点，范围为1--len
        for (int i = 1; i <= len ; i++) {
            for (int j = 0; j < i; j++) {
                if(wordDict.contains(s.substring(j, i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[len];
    }

    boolean flag = false;
    public boolean wordBreak1(String s, List<String> wordDict) {
        int n = s.length();  //目标字符串的长度
        /**
         * 回溯  超时
         * */
        backTrack(s,wordDict, new ArrayList<String>(),0,n);
        return flag;
    }

    void backTrack(String s, List<String> wordDict, List<String> list, int len, int n){
        //剪枝,当长度超出返回
        if (len>n){
            return;
        }

        if(len==n){
            StringBuilder str = new StringBuilder();
            for (String s1 : list) {
                str.append(s1);
            }
            if(str.toString().equals(s)){
                flag=true;
            }
            return;
        }
        for (int i = 0; i < wordDict.size(); i++) {
            list.add(wordDict.get(i));
            len += wordDict.get(i).length();
            backTrack(s, wordDict, list, len, n);
            list.remove(list.size()-1);  //回溯
            len -= wordDict.get(i).length();
        }

    }


}
//leetcode submit region end(Prohibit modification and deletion)
